package com.mdnote.practice.tire;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/24 
 * @description 单词搜索 II
 */
public class LeetCode212 {

    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};

    private TreeNode root;

    public static void main(String[] args) {
        LeetCode212 leetCode212 = new LeetCode212();
//        char[][] board = {
//                {'o','a','a','n'},
//                {'e','t','a','e'},
//                {'i','h','k','r'},
//                {'i','f','l','v'}
//        };
        char[][] board = {
                {'a','b'},
                {'a','a'},
        };

//        String[] word = {"oath", "pea", "eat", "rain"};
        String[] word = {"aba","baa","bab","aaab","aaa","aaaa","aaba"};
        List<String> list = leetCode212.findWords(board, word);
        list.forEach(System.out::println);
    }

    public List<String> findWords(char[][] board, String[] words) {
        // 用单词构建一颗Tire树
        this.root = new TreeNode();
        // 遍历word
        for (int i = 0; i < words.length; i++) {
            TreeNode cur = root;
            for (int j = 0; j < words[i].length(); j++) {
                // 把字符加入到树种
                if (cur.getChild(words[i].charAt(j)) == null) {
                    cur.setChild(words[i].charAt(j));
                }
                cur = cur.getChild(words[i].charAt(j));
            }
            cur.setEnd(true);
        }

        // 先找一下面板里面在root中存在的字符
        Set<String> set = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 在roo中存在，可以继续搜索
                if (root.getChild(board[i][j]) != null) {
                    dfs(i, j, "" + board[i][j], root.getChild(board[i][j]), board, set);
                }
            }
        }
        return new ArrayList<>(set);

    }

    private void dfs(int row, int column, String res, TreeNode node, char[][] board,  Set<String> list) {
        // Terminator
        if (node == null) {
            return;
        }
        if (node.isEnd()) {
            list.add(res);
            // 这里不能反悔哈 因为有坑是aaa  aaab
//            return;
        }

        // Process current logic
        char temp = board[row][column];
        board[row][column] = '@';
        for (int i = 0; i < dx.length; i++) {
            if (row + dx[i] >= 0 && row + dx[i] < board.length &&
                    column + dy[i] >= 0 && column + dy[i] < board[0].length &&
                    board[row + dx[i]][column + dy[i]] != '@') {
                // Drill down
                dfs(row + dx[i], column + dy[i], res + board[row + dx[i]][column + dy[i]], node.getChild(board[row + dx[i]][column + dy[i]]), board, list);

            }
        }
        // Restore current data
        board[row][column] = temp;
    }


    private static class TreeNode {
        private boolean end;
        private TreeNode[] children;

        public TreeNode() {
            this.children = new TreeNode[26];
        }

        private void setChild(char c) {
            this.children[c - 'a'] = new TreeNode();
        }

        public boolean isEnd() {
            return end;
        }

        public void setEnd(boolean end) {
            this.end = end;
        }

        public TreeNode getChild(char c) {
            return this.children[c - 'a'];
        }
    }
}
